#include <cstdio>

//greatest common divisor
template<typename T>
T gcd(T a, T b) {
	return (a&&b) ? gcd(b, a%b) : a+b;
}

//powermod(a, b, m) = a ^ b % m;
template<typename T>
T powermod(T a, T b, T m) {
	T p = 1, t = a;
	while (b > 0) {
		if (b & 1 == 1)
			p = p * t % m;
		t = t * t % m;
		b >>= 1;
	}
	return p;
}

int phi(int p) {
	return p - 1;
}
int PrimitiveRoot(int p) {
	int i, r, mul;
	if (2 == p) return 1;
	for (r = 2;r < p;r++) {
		mul = 1;
		for (i = 1; i < phi(p); i++) {
			mul = (mul * r) % p;
			if (1 == mul)
				break;
        }
		if (i == phi(p))
		return r;
	}
	return 0;
}
